package tree.test110;

import listbyorder.utils.TreeNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/16 13:09
 */
public class Solution2 {

    // 树形DP的解法
    class R {
        int h;
        boolean f;

        public R(int h, boolean f) {
            this.h = h;
            this.f = f;
        }
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        // 分别计算左右子树的高度
        R res = getR(root);
        return res.f;
    }

    private R getR(TreeNode node) {
        if (node == null) return new R(0, true);
        R l = getR(node.left);
        R r = getR(node.right);
        boolean f = (l.f && r.f && Math.abs(l.h - r.h) < 2);
        int h = Math.max(l.h, r.h) + 1;
        return new R(h, f);
    }
}
